class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int rh = minDepth(root->right);
        int lh = minDepth(root->left);
        if (!root->left && root->right) return rh + 1;
        if (root->left && !root->right) return lh + 1;
        return lh < rh ? lh + 1 : rh + 1;
    }
};